# -*- coding:utf-8 -*-
'''
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

解题思路：先算左半边，再算右半边 然后两两相乘
'''
class Solution:
    def __init__(self):
        self.B = []
    def multiply(self, A):
        # write code here
        # if not A: return self.B
        # for i in range(0,len(A)):
        #     cur = 1
        #     for x in A[:i]:
        #         cur = x*cur
        #     for y in A[i+1:]:
        #         cur = y*cur
        #     self.B.append(cur)
        # return self.B

        left = [1]
        right = [1]
        for i in range(len(A)-1):
            left.append(A[i]*left[i])
            right.append(A[-i-1]*right[i])
        res = [left[j]*right[-j-1] for j in range(len(A))]
        return res